Modular Arithmetic
13 Problems • 3 sub-topics
Adalynn Le • 5/15/2026
Table of Contents
Introduction
Modular arithmetic is the study and use opf operations and how they affect remainders. Modular arithmetic is a staple of number theory and complex questions on the AMC 10. In word problems, it is used to find leftovers or model cyclic operations and systems. In more numerically based problems, it is used to not just solve problems explicity related to number theory and modular arithmetic , but also to compare the relationships between numbers and shorten the time it takes to solve a problem.
Prime Factorization and Factors
To understand prime factorization, it is first important to understand how numbers work, and particularly how they work when divided. A number is considered evenly divisible by an integer when dividng by that integer yields another integer. If \(b\) evenly divides \(a\), it can be said that \(a \equiv 0 \textup{ mod}(b)\) In modular arithmetic, we will only ever work with integers. If a number is not evenly divisible by an integer the quotient (result) will have some fractional or decimal part. It is also said that the number leaves a remainder. The fractional/decimal part is found by \(\frac{\textup{remainder}}{\textup{divisor}}\). The integers that evenly divide a number are known as factors, and each factor can be found via prime factorization. Prime factorization is the process of systematically breaking down a number into a product of prime numbers that may or may not be raised to powers \(> 1\). For example, the prime factoriation of \(100\) is \(2^2 \times 5^2\). That is not to say that the only factors are two and five though, but those are the only prime factors. The total number of factors can be found by raising each power by one and multiplying. For a prime factorization of \(2^2 \times 5^2\), we see both prime factors raised to two so we find \(3 \times 3 = 9\) (which we can check by finding the factors of \(100: 1, 2, 4, 10 20, 25, 50, 100\)). Note that all numbers EXCEPT for perfect squares will have an even number of divisors because divisors often come in pairs The reason that this works is pretty simple: for each prime factor anywhere from \(0\) to the highest power of that can be present as a factor of the new factor. Thus, we raise to \(n+1\). We do this for all and multiply, following the primary idea and operation of counting.
How to Do Prime Factorization
There are many ways to do prime factorization, but I always prefer using factor trees. These are systematically structured processes that include "splitting" a number into two factors, then spliting those factors again and again until you get down to prime factors. This particularly helps stay organized. if possible, I recommend splitting into the smallest prime factors when possible, because that will limit the number of branches on your factor tree.
Prime Factor Tree Generator
Why is This Important?
Modular arithmeitc is heavily reliant of division and factors. It is important to know what the factors of a number will be, and thus understand what the values for \(\textup{mod} 0\) are. By knowing the prime factorization of a number, you can also predict how it will "act" when divided by numbers. For example, you may benefit from knowing if it is a perfect square, or if it is even, or has \(5\) as a divisor, etc. Prime factorization and modular arithmetic make the base of number theory.
Modular Congruency
Two numbers are considered modularly congruent if they \(\equiv\) the same value \(\textup{mod }(b)\). That is to say, when divided by some number \(b\), it leaves the same remainder. Albeit a seemingly simple qualification modularly congruent values can reveal a lot about a number and it's interactions with other numbers. A common visualization of modular arithmetic is that of an analog clock. Even though we live in a \(24\) hour day cycle, the clock only includes \(12\) points and loops around. Thus, the time \(6 \textup{ am}\) looks the same as \(6 \textup{ pm}\), which can also be written as \(18:00\) in military time. This is because \(18 \equiv 6 \textup{ mod }(12)\). Notice that modular congruency is reflexive and reflective meaning \(a \equiv a\) and \(a \equiv b \textup{ mod }(n)\), then \(b \equiv a \textup{ mod }(n)\).
Modular congruency forms the base of modular arithmetic, because the changes in modular arithmetic can be changed by arithmetic operations.
Operations w/ Modular Arithmetic
The study of modular arithmetic in its definition refers to how the remainders of numbers modulo \(n\) change as a result of arithmetic.
Addition
For \(a \equiv b \textup{ mod }(n)\) and \(c \equiv d \textup{ mod }(n)\), we have \(a \pm c \equiv b \pm d \textup{ mod }(n)\). The proof for this is rather intuitive, of course, you could deduce it through induction, but also consider that leaving a remainder means \(\textup{dividend} = \textup{divisor} \times \textup{divisor} + \textup{remainder}\). When you add two numbers, it becomes \(\textup{divisor}_{1} \times \textup{factor}_{1} + \textup{remainder}_{1}+\textup{divisor}_{2} \times \textup{factor}_{2} + \textup{remainder}_{2}\) with the point being that you add the remainders regardless, and it doesn't matter whta the divisors and factors are because what it ends up as is \(\textup{dividend}-\textup{remainder}\), so when you're comparing, it's the same thing and you can "factor it out" in a way.
Multiplication
\((a \times b) \textup{ mod }(N) = a \textup{ mod }(N) \times b \textup{ mod }(N)\). The full algebraic proof is pretty extensive, so I'm not going to prove it here, but the conceptual premise is if you expand the RHS without the modulo, then divide by \(n\), it will always work out the same, and you can prove it with variables
Negative Numbers
Negative numbers still have positive modulo remainder's, but it's not the same as the remainder For \(a \equiv b \textup{mod }(n)\) where \(|a| \leq n\), \(b=n-|a|\). For \(|a| \geq n\), you would find the remainder when dividing by \(\frac{|a|}{n}\), then take the negative of that number and the modulo of that with respect to \(n\)
The most effective use of modular arithmetic is if you know two numbers are the same \(\textup{mod }(n)\), and you are doing a problem that doesn't deal with specific values, you can substitute smaller or simpler values. The properities of modularly congruent numbers remain unchanged and thus allow you to manipulate them to make problems more simple, in addition to solving explicitly modular arithmetic problems
Conclusion
Modular Arithmetic is the basis of number theory as a whole. It provides an understanding of the relationships and interactions between numbers that is nescessary to fully perform well on the AMC 10 and understand the function of numbers. With modular operations and substitution, modular arithmetic really is it's own field of study and theory.
Question 1:
Loading question...
Welcome Back!
Access your progress across all your devices
Need Some Help?
Contact us through our form